package com.study.algorithm.sort;

import java.util.Arrays;

/**
 * 插入排序。
 *
 * <p><B>排序原理：</B>
 * <ol>
 *   <li>把所有的元素分为两组，已知排序的和未排序的。</li>
 *   <li>找到未排序的组中的第一个元素，向已经排序的组中进行插入。</li>
 *   <li>倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待
 * 插入元素放到这个位置，其他的元素向后移动一位。</li>
 * </ol>
 *
 * <p><B>时间复杂度分析：</B>插入排序使用了双层for循环，其中内层循环的循环体是真正完成排序的代码，所以，我们分析插入排序的时间复
 * 杂度，主要分析一下内层循环体的执行次数即可。
 *
 * <p>最坏情况，也就是待排序的数组元素为 {@code {12,10,6,5,4,3,2,1}}，那么：
 * 比较的次数为：{@code (N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2}，
 * 交换的次数为：{@code (N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2}，
 * 总执行次数为：{@code (N^2/2-N/2)+(N^2/2-N/2)=N^2-N}。
 * 按照大O推导法则，保留函数中的最高阶项那么最终插入排序的时间复杂度为 {@code O(N^2)}。
 *
 * @author chenganbang
 */
public class Insertion implements Sort {

  private Insertion() {
  }

  private static class Holder {
    private static final Insertion INSTANCE = new Insertion();
  }

  public static Insertion getInstance() {
    return Insertion.Holder.INSTANCE;
  }

  /**
   * 对数组 source 进行排序。
   *
   * <p>假设待排序数组：[9, 1, 2, 5, 7, 4, 8, 6, 3]，那么排序过程如下：
   * <ul>
   * <li>第 1 趟排序结果（插入1）：[<B>1</B>, 9, 2, 5, 7, 4, 8, 6, 3]
   * <li>第 2 趟排序结果（插入2）：[1, <B>2</B>, 9, 5, 7, 4, 8, 6, 3]
   * <li>第 3 趟排序结果（插入5）：[1, 2, <B>5</B>, 9, 7, 4, 8, 6, 3]
   * <li>第 4 趟排序结果（插入7）：[1, 2, 5, <B>7</B>, 9, 4, 8, 6, 3]
   * <li>第 5 趟排序结果（插入9）：[1, 2, 4, 5, 7, <B>9</B>, 8, 6, 3]
   * <li>第 6 趟排序结果（插入8）：[1, 2, 4, 5, 7, <B>8</B>, 9, 6, 3]
   * <li>第 7 趟排序结果（插入6）：[1, 2, 4, 5, <B>6</B>, 7, 8, 9, 3]
   * <li>第 8 趟排序结果（插入3）：[1, 2, <B>3</B>, 4, 5, 6, 7, 8, 9]
   * </ul>
   * 排好序结果：[1, 2, 3, 4, 5, 6, 7, 8, 9]
   *
   * @param source
   *     数组 source
   */
  @Override
  public void sort(Comparable[] source) {
    System.out.println("待排序数组：" + Arrays.toString(source));

    SortHelper sortHelper = SortHelper.getInstance();
    for (int i = 1; i < source.length; i++) {
      for (int j = i; j > 0; j--) {
        if (sortHelper.greater(source[j - 1], source[j])) {
          sortHelper.exchange(source, j - 1, j);
        } else {
          break;
        }
      }
      sortHelper.printArray(i, source);
    }

    System.out.println("排好序结果：" + Arrays.toString(source));
  }
}